285. Inorder Successor in BST
Medium

Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.

The successor of a node p is the node with the smallest key greater than p.val.

 

Example 1:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -105 <= Node.val <= 105
  • All Nodes will have unique values.
Accepted
210.4K
Submissions
474.5K
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.44 (27 votes)

Premium

Solution


Overview

This is a very popular programming interview problem and there are a couple of ways we can approach it. This problem is very similar to finding the Inorder Successor in a Binary Tree. The first solution that we will look at applies to any kind of binary tree because it does not rely on any special properties of the tree. Our second solution will take into account the sorted nature of the binary search tree and will thus, improve upon the overall time complexity of the previous solution. The inorder successor of a particular node is simply the node that comes after this node during the inorder traversal of the tree. There are a few scenarios that we must consider for the inorder successor of a node to understand our first algorithm properly.

Few examples of inorder successors

Figure 1. Few examples of inorder successors.

Inorder example

Figure 2. Another unique example of an inorder successor.



Approach 1: Without using BST properties

Intuition

As mentioned in the overview section of this article, we will first discuss the approach that applies to any binary tree and is not specifically for a binary search tree. This is not the most efficient approach out there considering it doesn't incorporate the search properties associated with the structure of a binary search tree. However, for the sake of completeness, we are including this approach in the official solution since the interviewer may ask you to find the inorder successor for a binary tree :)

We hinted briefly at the different cases for the inorder successor and we will look at these cases more concretely in this solution. The algorithm is based on handling these cases one by one. There are just two cases that we need to account for in this approach.

When the node has a right child

The inorder successor in this case is the leftmost node in the tree rooted at the right child. Let's look at a couple of examples to depict this point.

Case 1

Figure 3. Case 1 when the given node has a right child.

Let's look at yet another example where there is a right child who doesn't have a left child. In this case, the right child itself will be the inorder successor of the designated node.

Case 1

Figure 4. Another example of when the node has a right child.

When the node doesn't have a right child

This is trickier to handle than the first case. In this case, one of the ancestors acts as the inorder successor. That ancestor can be the immediate parent, or, it can be one of the ancestors further up the tree.

Case 2

Figure 5. When the node does not have the right child.

In this case, we need to perform the inorder traversal on the tree and keep track of a previous node which is the predecessor to the current node we are processing. If at any point the predecessor previous is equal to the node given to us then the current node will be its inorder successor. Why? Because we are performing the inorder traversal on the tree to find the successor node via simulation.

Algorithm

  1. We define two class variables for this algorithm: previous and inorderSuccessorNode. The previous variable will only be used when handling the second case as previously explained and the inorderSuccessorNode will ultimately contain the result to be returned.

  2. Inside the function inorderSuccessor, we first check which of the two cases we need to handle. For that, we simply check for the presence of a right child.

    • The right child exists

      In this case, we assign the right child to a node called leftmost and we iterate until we reach a node (leftmost) which doesn't have a left child. We iteratively assign leftmost = leftmost.left and that's how we will get the leftmost node in the subtree.

    • The right child does not exist

      1. As mentioned before, this case is trickier to handle. For this, we define another function called inorderCase2 and we will pass it a node and the node p.
      2. We perform simple inorder traversal and hence, we first recurse on the left child of the node.
      3. Then, when the recursion returns, we check if the class variable previous is equal to the node p. If that is the case, then it means p is the inorder predecessor of node or in other words, the node is the inorder successor of the node p and we return from that point onwards. We assign inorderSuccessorNode to node and return from this function.
  3. Finally, we return the inorderSuccessorNode as our result.

Implementation

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of nodes in the tree.

    • For case 1, we might have a scenario where the root node has a right subtree that is left-skewed. Something like the following.

      Time complexity skewed

      Figure 6. A skewed tree for worst-case time complexity.

      In this case, we have to process all of the nodes to find the leftmost node and hence, the overall time complexity is O(N)O(N).

    • For case 2, we might have to process the entire tree before finding the inorder successor. Let's look at an example tree to understand when that might happen.

      Time complexity skewed

      Figure 7. A skewed tree for worst-case time complexity.

  • Space Complexity: Space Complexity: O(N)O(N) for the second case since we might have a skewed tree leading to a recursion stack containing all NN nodes. For the first case, we don't have any additional space complexity since we simply use a while loop to find the successor.


Approach 2: Using BST properties

Intuition

In the previous approach, we did not use any of the binary-search tree properties. However, the optimal solution for this problem comes from utilizing those properties and that's what we will explore in this solution. Specifically, we'll make use of the standard BST property where the left descendants have smaller values than the current node and right descendants have larger values than the current node. We don't need to handle any specific cases here and we can start with the root node directly and reach our inorder successor. Let's see the choices we have when comparing the value of the given node p to the current node in the tree.

BST property depiction

Figure 8. Skipping half of the binary search tree.

By comparing the values of the node p and the current node in the tree during our traversal, we can discard half of the remaining nodes at each step, and thus, for a balanced binary search tree we can search for our inorder successor in logarithmic time rather than linear time. That's a huge improvement over the previous solution.

Algorithm

  1. We start our traversal with the root node and continue the traversal until our current node reaches a null value i.e. there are no more nodes left to process.

  2. At each step we compare the value of node p with that of node.

    1. If p.val >= node.val that implies we can safely discard the left subtree since all the nodes there including the current node have values less than p.

      Skipping the left subtree

      Figure 9. Skipping the left subtree.

    2. However, if p.val < node.val, that implies that the successor must lie in the left subtree and that the current node is a potential candidate for inorder successor. Thus, we update our local variable for keeping track of the successor, successor, to node.

      Skipping the right subtree

      Figure 10. Skipping the right subtree and recording a potential candidate for the successor.

  3. Return successor.

    Returning the candidate.

    Figure 11. Returning the candidate.

We don't handle duplicate node values in the algorithm below. That is left as an exercise for the reader to solve :) It's a slight variation but an important one to understand for follow-up questions in an interview.

Implementation

Complexity Analysis

  • Time Complexity: O(N)O(N) since we might end up encountering a skewed tree and in that case, we will just be discarding one node at a time. For a balanced binary-search tree, however, the time complexity will be O(logN)O(\text{log}N) which is what we usually find in practice.

  • Space Complexity: O(1)O(1) since we don't use recursion or any other data structures for getting our successor.

Report Article Issue

Comments: 7
Goldspear's avatar
Read More

Combine the two solutions to allow earlier stopping:

  1. If p has a right leaf, we only need to traverse from p to leaf (one step right, all step left)
  2. Else, we only need to traverse from root to p
def inorderSuccessor_02(root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
    if p.right:
        curr = p.right
        while curr.left:
            curr = curr.left
        return curr
    else:
        successor, curr = None, root
        while curr != p:
            if curr.val < p.val:
                curr = curr.right
            else:
                successor, curr = curr, curr.left
        return successor

5
Reply
Share
Report
brucewen05's avatar
Read More

Can someone help me understand how to tweak solution 2 to handle duplicates?
Does it depend on how we treat duplicate values? i.e. whether we choose to insert a node with equal value to its parent on the left or right?

It seems to me solution 1 is a more general solution although it uses more space due to recursion.

5
Show 3 replies
Reply
Share
Report
unknown1234's avatar
Read More

(Not using BST property) just take the next of p during the inorder traversal:

    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        
        curr=root
        stack=[]
        turn=False
        while curr or stack:
            while curr:
                stack.append(curr)
                curr=curr.left
            # curr=None
            # stack top is the left most
            node=stack.pop()
            if node.right:
                curr=node.right
                
            if turn:
                return node
            
            if node==p:
                turn=True

1
Reply
Share
Report
devanother's avatar
Read More

I got both, the iterative and the recursive approaches and felt like my recursive approach was simpler than what they have put here. My iterative one was quite similar to their but still simpler imo.

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null){
            return null;
        }
        
        TreeNode successor = inorderSuccessor(root.left, p);
        if(successor != null){
            return successor;
        }
        
        if(root.val > p.val){
            return root;
        }
        
        return inorderSuccessor(root.right, p);
    }
}

0
Reply
Share
Report
Rk_13's avatar
Read More

Simple and concise Recursive solution using BST property( C++)

class Solution {  
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode *candidate = NULL;
        TreeNode *cur = root;
        
        while(cur != NULL){
            if(cur->val > p->val){
                candidate = cur;
                cur = cur->left;
            }
            else{
                cur = cur->right;
            }
        }
        return candidate;
    }
};

0
Show 1 reply
Reply
Share
Report
tirthpatel98's avatar
Read More

In approach 1, handling cases was not really required. Second case (with some minor changes) would have need enough.

0
Show 1 reply
Reply
Share
Report
Bhosdiwalechacha's avatar
Read More

```def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
    
    
    def _helper(root, p, curr_val):
        if not root:
            return curr_val

        else:
            if root.val > p.val:
                return _helper(root.left, p, root)
                
            else:
                return _helper(root.right, p, curr_val)
    
    return _helper(root, p, None)  

-3
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.